'''
查找：给定一个序列，查找里面的元素
顺序查找：按照序列的元素存储顺序，挨个查找
    优点：不需要排序
    缺点：可能将里面的元素全部遍历，速度慢
二分查找：快  序列必须是排序后的序列才行
    优点：查找速度快
    缺点：序列有个前提，必须是排序后的序列
'''
list1= ["lily","tom","lucy","jack","阿黄","二蛋"]
# 查找列表中的元素，如果找到了，打印找到了
def search(ls,key):
    for i in ls:
        if i == key:
            return "找到了"
    return "没找到"

print(search(list1,"tom1"))

'''
二分查找
  ls =   1  3  4  6  7  9  12  45  67  68  79    key 34  45
                        9(列表的中间数据9和可以比较)
  ls =   12  45 67 68 79  （9后面的数据成新的列表）
                67（67比key大）
  ls =  12  45
            45（45比key大）
  ls = 12
       12（12比key小）
  ls = []  空的列表就不需要比较了 没找到         
'''
"递归 循环"
def search1(ls,key):
    if ls ==[]:
        return "没找到"

    # 找到中间下标
    mid = len(ls)//2
    print("下标",mid,ls[mid])
    # 根据中间下标对应的值和key判断
    if ls[mid] == key:
        # print("---找到了-------")
        #  中间值=key  找到了
        return "找到了"
    #  中间值>key  往前找 改变列表，重新调用search1（）
    elif ls[mid] > key:
        return search1(ls[0:mid:],key)
    #  中间值<key  往后找 改变列表
    else:
        return search1(ls[mid+1::], key)

ls = [1,2,3,5,7,8,53,56,78,89]
print(search1(ls,21))

'''
循环
   1  3  4  6  7  9  12  45  67  68  79    key 34  68
   l              m                  r
                     l       m       r
                     l   m,r
                     l,r,m  查找结束 
                     
                     
   l               m                  r  
                     l       m        r
                                l,m   r 找到了
                                       
'''
ls1 = [1,2,3,5,7,8,53,56,78,89]
def search2(ls,key):
    # 设置三个变量
    r = len(ls)-1  # 下标最大值
    l = 0

    while l <= r:
        m = (l+r) // 2
        # 判断m对应的元素和 key比较
        if ls[m] == key:
            return "找到了"
        elif ls[m] > key: # 往前查找 l不变 r为m前一个
            r = m-1
        else:
            l = m+1
    return "没找到"

print(search2(ls1,3))
print(search2(ls1,89))


